﻿#pragma once
#include "stdafx.h"

/*
括号生成 中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

 示例：

 输入：n = 3
 输出：[
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
 ]

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/generate-parentheses
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 解题思路：看到遍历所有的情况，就要想到采用回溯的方法，每次采取一个，所有可能的东西全部找到。
 下面是回溯的方式。
*/

void backString(vector<string>& res, string & str, int open, int close, int num)
{
	if (str.size() == num * 2)
	{
		res.push_back(str);
		return;
	}

	if (open < num)
	{
		str.push_back('(');
		backString(res,str,open+1,close,num);
		str.pop_back();
	}

	if (close < open)
	{
		str.push_back(')');
		backString(res, str, open, close+1, num);
		str.pop_back();
	}

}

vector<string> generateParenthesis(int n)
{
	vector<string> result; //输出结果放在这里
	string str=""; //字符串临时
	backString(result, str,0,0,n);
	return result;
}

void testgenerateParenthesis()
{
	int n = 3;
	vector<string> strs = generateParenthesis(n);

	for ( const auto & i:strs )
	{
		cout << i << endl;
	}
}

/*

((()))
(()())
(())()
()(())
()()()

*/